package array.binarySearch;
/**
 * 题目:给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
       由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
       注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * 解题方法: 二分法
 */

/**以下为我自己的解法，得用二分法优化
 * class Solution {
 *     public int mySqrt(int x) {
 *         long res=1;
 *         while(res*res<=x){
 *             if(res*res==x){
 *                 return (int)res;
 *             }
 *             res++;
 *         }
 *         return (int)(res-1);
 *     }
 * }
 */

public class squareRoot  {
    public int mySqrt(int x) {
        //处理特殊情况
        if(x==0){
            return 0;}

        int left=1;
        int right = x;

        while(left<=right){
            int mid=(left+right)/2;

            //注意:此处不使用mid*mid的原因是因为当其超过Integer.MAX_VALUE时，会溢出(2,147,483,647)
            if(mid > x / mid){
                right=mid-1;}
            else if(mid < x / mid){
                left=mid+1;}
            else{
                return mid;}}

        return right;

    }
}